// m

// 给定代表不同面额的硬币数组coins和一个总金额amount
// 要求：计算并返回可以凑成总金额的硬币组合数，如果无法凑出总金额，则返回0
// 假定：每一种面额的硬币枚数为无限个

// 零钱兑换是计算凑成总金额的最少硬币个数，而这道题是凑成总金额的硬币组合数
// 可以转换为n枚不同的硬币，每种硬币可以无限次使用，凑成总结为amount的背包，总共有多少组合方式
// 动态规划dp[i]可以表示凑成总金额为i的组合数
// 动态规划的转移方程为dp[i] = dp[i] + dp[i- coin]
// 意思是，凑成总金额为i的组合数 = 不使用当前coin，只使用之前硬币凑成金额i的组合数 + 使用当前coin凑成金额 i - coin的方案数

function change(amount, coins) {
    let dp = new Array(amount + 1).fill(0)
    dp[0] = 1
    for (let i = 0; i < coins.length; i++) {
        for (let j = coins[i]; j < amount + 1; j++) {
            dp[j] += dp[j - coins[i]]
        }
    }
    return dp[amount]
}

let amount = 5, coins = [1, 2, 5]
console.log(change(amount, coins))